#pragma once

#include <initializer_list>
#include "functor.hpp"
#include "utility.hpp"
#include "list_node.hpp"
#include "log_functor.hpp"
#include "allocator.hpp"

namespace zuck
{
	template<typename _List>
	class _ForwardListConstIterator {
	public:
		using value_type        = typename _List::value_type;
		using pointer		    = const value_type*;
		using reference         = const value_type&;
		using difference_type	= typename _List::difference_type;
		using iterator_category = zuck::forward_iterator_tag;
	private:
		using _Node_ptr = __list_node<value_type>*;
		using _Self     = _ForwardListConstIterator<_List>;
	private:
		_Node_ptr _m_iter;
		_Node_ptr _m_end;
	public:
		explicit _ForwardListConstIterator(_Node_ptr iter, _Node_ptr end)
			:_m_iter(iter), _m_end(end) {}

		_ForwardListConstIterator(const _Self& other)
			:_m_iter(other._m_iter), _m_end(other._m_end)
        {}

		_ForwardListConstIterator(_Self&& other) noexcept
			:_m_iter(other._m_iter), _m_end(other._m_end)
        {}

		inline virtual ~_ForwardListConstIterator()
		{
			_m_iter = null;
			_m_end  = null;
		}

		inline _ForwardListConstIterator& operator=(const _Self& other)
		{
			_m_iter = other._m_iter;
			_m_end  = other._m_end;
			return *this;
		}

		inline _ForwardListConstIterator& operator=(_Self&& other)noexcept
		{
			_m_iter = other._m_iter;
			_m_end  = other._m_end;
			other._m_iter = null;
			other._m_end  = null;
			return *this;
		}

		inline _ForwardListConstIterator& operator++()noexcept
		{
			if constexpr (debug_) {
				if (!_m_iter) {
					debug_log::derror(zuck::SEG_WrongIter, 
						"Segmentfault: invalid pointer !");
				}
			}
			_m_iter = _m_iter->_m_n;
			return *this;
		}

		[[nodiscard]] inline _ForwardListConstIterator operator++(int)noexcept
		{
			auto _Tmp = *this;
			++(*this);
			return ++_Tmp;
		}

		[[nodiscard]] inline _Node_ptr get_unwrapped()noexcept
		{
			return _m_iter;
		}

		[[nodiscard]] inline pointer operator->()const noexcept
		{
			if constexpr (debug_) {
				if (!_m_iter) {
					debug_log::derror(zuck::SEG_WrongIter,
						    "Segment fault: _m_iter is nullptr");
				}
			}
			return _m_iter->_m_data;
		}

		[[nodiscard]] inline reference operator*()const noexcept
		{
			if constexpr (debug_) {
				if (!_m_iter) {
					debug_log::derror(zuck::SEG_WrongIter,
						"Segment fault: _m_iter is nullptr");
				}
			}
			return *(_m_iter->_m_data);
		}

		[[nodiscard]] inline bool operator==(_Self const& other)const noexcept
		{ return static_cast<bool>(_m_iter == other._m_iter); }

		[[nodiscard]] inline bool operator!=(_Self const& other)const noexcept
		{ return static_cast<bool>(_m_iter != other._m_iter); }
	};


	template<typename _List>
	class _ForwardListIterator : public _ForwardListConstIterator<_List>
	{
	private:
		using _Base = _ForwardListConstIterator<_List>;
		using _Self = _ForwardListIterator<_List>;
	public:
		using value_type		= typename _Base::value_type;
		using pointer			= value_type*;
		using reference			= value_type&;
		using difference_type	= typename _Base::difference_type;
		using iterator_category = typename _Base::iterator_category;
	private:
		using _Node_ptr = __list_node<value_type>*;
	public:
		explicit _ForwardListIterator(_Node_ptr iter, _Node_ptr end)
			: _Base(iter, end) {}

		_ForwardListIterator(_Self const& other) : _Base(other) {}

		_ForwardListIterator(_Self&& other)noexcept : _Base(zuck::move(other)) {}

		inline _Self& operator=(_Self const& other) {
			_Base::operator=(other);
			return *this;
		}

		inline _Self& operator=(_Self&& other)noexcept {
			_Base::operator=(zuck::move(other));
			return *this;
		}

		[[nodiscard]] inline pointer operator->()noexcept {
			return const_cast<pointer>(_Base::operator->());
		}

		[[nodiscard]] inline reference operator*()noexcept {
			return const_cast<reference>(_Base::operator*());
		}

		inline _Self& operator++()noexcept {
			_Base::operator++();
			return *this;
		}

		[[nodiscard]] inline _Self& operator++(int)noexcept {
			auto _Tmp = *this;
			_Base::operator++();
			return *this;
		}

	};

	template<typename T, typename Alloc = zuck::allocator<T>>
	class forward_list {
	private:
		using _Self		   = zuck::forward_list<T, Alloc>;
		using _Node_ptr    = zuck::__list_node<T>*;
		using _Node_Alloc  = zuck::__list_node<T>;
		using _Alty_tts = zuck::allocator_traits<zuck::allocator<T>>;
	public:
		using value_type		= typename _Alty_tts::value_type;
		using pointer			= typename _Alty_tts::pointer;
		using const_pointer		= typename _Alty_tts::const_pointer;
		using reference			= typename _Alty_tts::reference;
		using const_reference	= typename _Alty_tts::const_reference;
		using allocator_type    = typename _Alty_tts::template rebind_alloc<T>;
		using size_type			= zuck::size_t;
		using difference_type	= zuck::ptrdiff_t;
	public:
		using iterator		 = _ForwardListIterator<forward_list<T, Alloc>>;
		using const_iterator = _ForwardListConstIterator<forward_list<T, Alloc>>;
	private:
		_Node_ptr _m_head;
		_Node_ptr _m_tail;
		size_type _m_cnt;
		Alloc    alloc;
	public:
		explicit forward_list()
			: _m_head(), _m_tail(), _m_cnt(0), alloc(Alloc{}) {}

		explicit forward_list(size_type size_, const T& val)
			: _m_head(), _m_tail(), _m_cnt(0), alloc(Alloc{})
		{
			__construct_n(size_, val);
		}

		explicit forward_list(size_type size_, Alloc al)
			: _m_head(null), _m_tail(null), _m_cnt(0), alloc(Alloc{})
		{
			__construct_n(size_, T{});
		}

		forward_list(std::initializer_list<T> data)
			: _m_head(null), _m_tail(null), _m_cnt(0), alloc(Alloc{})
		{
			__construct_range(data.begin(), data.end());
		}

		explicit forward_list(std::initializer_list<T> data, Alloc al)
			: _m_head(null), _m_tail(null), _m_cnt(0), alloc(al)
		{
			__construct_range(data.begin(), data.end());
		}

		template<typename InputIterator,
			zuck::enable_if_t<zuck::is_iterator_v<InputIterator>, int> = 0>
		explicit forward_list(InputIterator Begin, InputIterator End)
			: _m_head(null), _m_tail(null), _m_cnt(0), alloc(Alloc{})
		{
			__construct_range(Begin, End);
		}

		template<typename InputIterator,
			zuck::enable_if_t<zuck::is_iterator_v<InputIterator>, int> = 0>
		explicit forward_list(InputIterator Begin, InputIterator End, Alloc al)
			: _m_head(null), _m_tail(null), _m_cnt(0), alloc(al)
		{
			__construct_range(Begin, End);
		}

		forward_list(const forward_list& other)
			:_m_head(null), _m_tail(null), _m_cnt(0)
		{
			assign(other.begin(), other.end());
		}

		forward_list(forward_list&& other)noexcept
			:_m_head(other._m_head), _m_tail(other._m_tail), _m_cnt(other._m_cnt)
		{
			other._m_head = null;
			other._m_tail = null;
			other._m_cnt  = 0;
		}

		inline ~forward_list() { __destroy(); }

	public:
		void assign(const size_type _NewSize, const T& val)
		{
			auto const _OldSize = size();
			auto _Begin			= begin();
			auto const _End		= end();
			__verify_size(_NewSize);
			if (_NewSize > _OldSize) {
				zuck::fill(_Begin, _End, val);
				for (int i = 0; i < _NewSize - _OldSize; ++i) {
					__emplace_back(val);
				}
				return;
			}
			__free_tail_n(_OldSize - _NewSize);
			zuck::fill(_Begin, end(), val);
		}

		void assign(std::initializer_list<T> data)
		{
			__assign_range(data.begin(), data.end());
		}

		template<typename InputIterator>
		void assign(InputIterator Begin, InputIterator End)
		{
			__assign_range(Begin, End);
		}

		[[nodiscard]] inline iterator begin()noexcept
		{
			return iterator(_m_head, _m_tail);
		}

		[[nodiscard]] inline const_iterator begin()const noexcept
		{
			return const_iterator(_m_head, _m_tail);
		}

		[[nodiscard]] inline const_iterator cbegin()const noexcept
		{
			return const_iterator(_m_head, _m_tail);
		}

		[[nodiscard]] inline iterator end()noexcept
		{
			return iterator(null, _m_tail);
		}

		[[nodiscard]] inline const_iterator end()const noexcept
		{
			return const_iterator(null, _m_tail);
		}

		[[nodiscard]] inline const_iterator cend()const noexcept
		{
			return const_iterator(null, _m_tail);
		}

		inline void clear() { __destroy(); }

		[[nodiscard]] inline T& front()noexcept
		{
			return *(_m_head->_m_data);
		}

		[[nodiscard]] inline const_reference front()const noexcept
		{
			return *(_m_head->_m_data);
		}

		[[nodiscard]] inline T& back()noexcept
		{
			return *(_m_tail->_m_data);
		}

		[[nodiscard]] inline const_reference back()const noexcept
		{
			return *(_m_tail->_m_data);
		}

		[[nodiscard]] inline allocator_type get_allocator()const noexcept
		{
			return Alloc{};
		}

		void insert(const_iterator& Where, const T& val)
		{
			return __emplace_aux(val, 2, Where);
		}

		void insert(const_iterator& Where, T&& val)
		{
			return __emplace_aux(val, 2, Where);
		}

		inline void push_front(const T& val)
		{
			__emplace_front(val);
		}

		inline void push_front(T&& val)
		{
			__emplace_front(zuck::move(val));
		}

		template<typename ...Args>
		inline T& emplace_front(Args&&...args)
		{
			return *__emplace_front(zuck::forward<Args>(args)...);
		}

		template<typename ...Args>
		inline iterator emplace(Args&&...args)
		{
			return __emplace_aux(zuck::forward<Args>(args)...);
		}

		void pop_front()
		{ __destroy_begin(); }

		template<typename _Cmp = zuck::less<T>>
		void sort(_Cmp const& _pred = zuck::less<T>{})
		{
			for (_Node_ptr _Indi = _m_head; _Indi != null; _Indi = _Indi->_m_n) {
				_Node_ptr _Tmp = _Indi;
				for (_Node_ptr _Indj = _Indi->_m_n; _Indj != null; _Indj = _Indj->_m_n) {
					if (_pred(*(_Indj->_m_data), *(_Tmp->_m_data))) {
						_Tmp = _Indj;
					}
				}
				if (_Tmp != _Indi) {
					zuck::swap(_Tmp->_m_data, _Indi->_m_data);
				}
			}
		}
		
		[[nodiscard]] iterator find(const T& val)
		{
			_Node_ptr tmp = _m_head;
			for (; tmp; tmp = tmp->_m_n) {
				if (tmp->_m_data == val) {
					return iterator(tmp, _m_tail);
				}
			}
			return iterator{};
		}

		[[nodiscard]] inline size_type size()const noexcept
		{ 
			return _m_cnt;
		}
		
		[[nodiscard]] inline size_type max_size()const noexcept
		{
			return __size<T>::max_size();
		}

		[[nodiscard]] inline bool empty()const noexcept
		{
			return (!_m_cnt || !_m_head);
		}

		void resize(const size_type _Newsize, const T& val = T{})
		{
			auto const _Max = max_size();
			if (_Newsize > _Max) {
				derror(zuck::SEG_LengthTooLong, "parameter's size too long !");
			}
			auto const _Size = size();
			if (_Newsize > _Size) {
				for (size_type i = 0; i < _Newsize - _Size; ++i) {
					__emplace_back(val);
				}
				return;
			}
			__free_tail_n(_Size - _Newsize);
		}

		void reverse()
		{
			for (_Node_ptr _Tmpi = _m_head, _Tmpj = _m_tail;
				 _Tmpi != _Tmpj;
				 _Tmpi = _Tmpi->_m_n, _Tmpj = _Tmpj->_m_p)
			{
				zuck::swap(_Tmpi->_m_data, _Tmpj->_m_data);
			}
		}

		iterator remove(const_iterator wh)
		{
			_Node_ptr ptr = wh.get_unwrapped();
			if (!ptr) {
				derror(zuck::SEG_OutofRange, "Invalid list node");
			}
			_Node_ptr _Tmp = ptr->_m_n;
			ptr->_m_p->_m_n = _Tmp;
			_Tmp->_m_p = ptr->_m_p;
			alloc.deallocate(ptr->_m_data, 1);
			_Node_Alloc::_Deallocate(ptr);
			return iterator(_Tmp);
		}

		void remove(const T& val)
		{
			_Node_ptr tmp = _m_head, pn = _m_head->_m_n;
			if (empty()) {
				return;
			}
			if (_m_head->_m_data == val && _m_head == _m_tail) {
				__destroy();
				_m_head = _m_tail = 0;
				return;
			}
			else if (_m_head->_m_data == val && _m_head->_m_n != null) {
				_Node_ptr tmp = _m_head;
				_m_head      = _m_head->_m_n;
				alloc.deallocate(tmp);
				return;
			}
			for (; pn != nullptr && tmp != nullptr;) {
				if (tmp->_m_data == val) {
					tmp->_m_data = tmp->_m_n->_m_data;
					tmp->_m_n    = tmp->_m_n->_m_n;
					alloc.deallocate(tmp->_m_n);
					break;
				}
				else if (tmp->_m_n == _m_tail && tmp->_m_n->_m_data == val) {
					tmp->_m_n = null;
					_m_tail   = tmp;
					alloc.deallocate(pn);
					break;
				}
				tmp = tmp->_m_n;
				pn  = pn->_m_n;
			}
			return;
		}

		inline void swap(_Self& other)noexcept
		{
			_Self _Tmp = zuck::move(other);
			other      = zuck::move(*this);
			*this      = zuck::move(_Tmp);
		}

		inline forward_list& operator=(const forward_list& other)
		{
			__construct_range(other.begin(), other.end());
			return *this;
		}

		inline  forward_list& operator=(forward_list&& other)noexcept
		{
			__move_construct(zuck::forward<_Self>(other));
			return *this;
		}

		bool operator==(const _Self& other)const noexcept
		{
			return static_cast<bool>((_m_cnt == other.size())
						&& __equal_with(other, zuck::equal_to<T>{}));
		}

		bool operator!=(const _Self& other)const noexcept
		{
			return static_cast<bool>((_m_cnt != other.size)
						|| __not_equal_with(other, zuck::not_equal_to<T>{}));
		}

	private:
		template<typename InputIterator>
		void __assign_range(InputIterator first, InputIterator last)
		{
			size_type const _Oldsize = size();
			size_type const _Newsize = zuck::distance(first, last);
			auto _First     = begin();
			auto const _End = end();
			__verify_size(_Newsize);
			_m_cnt = _Newsize;
			if (_Newsize > _Oldsize) {
				auto _Next = zuck::advance(first, _Oldsize);
				zuck::fill(first, last, _First, _End);
				for (auto i = _Next; i != last; ++i) {
					__emplace_back(*i);
				}
				return;
			}
			__free_tail_n(_Oldsize - _Newsize);
			zuck::fill(first, last, _First, _End);
		}

		void __destroy()
		{
			if (!_m_head) {
				return;
			}
			for (; _m_head->_m_p; _m_head = _m_head->_m_p);
			_m_head = _m_tail;
			for (; _m_tail;) {
				_m_head = _m_head->_m_n;
				alloc.deallocate(_m_tail->_m_data, 1);
				_Node_Alloc::_Deallocate(_m_tail);
				_m_tail = _m_head;
			}
			_m_cnt = 0;
		}

		void __destroy_data()
		{
			if (!_m_cnt) {
				return;
			}
			_m_tail = _m_head;
			for (; _m_tail; _m_tail = _m_tail->_m_n) {
				alloc.deallocate(_m_tail->_m_data);
			}
			_m_tail = _m_head;
		}

		inline void __move_construct(_Self&& other)
		{
			if (other.empty()) {
				__destroy();
			}
			_m_head = other._m_head;
			_m_tail = other._m_tail;
			_m_cnt  = other._m_cnt;
			other._m_head = null;
			other._m_tail = null;
			other._m_cnt  = 0;
		}

		template<typename ...Args>
		iterator __emplace_aux(iterator _where, Args&&... args)
		{
			__verify_size(_m_cnt);
			if (_where == begin()) {
				return __emplace_front(zuck::forward<Args>(args)...);
			}
			elif (_where == end()) {
				return __emplace_back(zuck::forward<Args>(args)...);
			}
			_Node_ptr __new = null;
			__new = _Node_Alloc::_Allocate(alloc.allocate(1));
			zuck::construct(__new->_m_data, zuck::forward<Args>(args)...);
			_Node_ptr _wh = _where.get_unwrapped();
			__new->_m_n    = _wh->_m_n;
			_wh->_m_n      = __new;
			++_m_cnt;
			return iterator(__new);
		}

		template<typename ...Args>
		iterator __emplace_front(Args&&... args)
		{
			if (!_m_head) {
				_m_head = _Node_Alloc::_Allocate(alloc.allocate(1));
				_m_tail = _m_head;
				zuck::construct(_m_head->_m_data, zuck::forward<Args>(args)...);
				++_m_cnt;
				return iterator(_m_head);
			}
			__verify_size(_m_cnt);
			if (!_m_head->_m_p) {
				_m_head->_m_p = _Node_Alloc::_Allocate(alloc.allocate(1), _m_head);
				_m_head = _m_head->_m_p;
				zuck::construct(_m_head->_m_data, zuck::forward<Args>(args)...);
				++_m_cnt;
				return iterator(_m_head);
			}
			_m_head = _m_head->_m_p;
			_m_head->_m_data = alloc.allocate(1);
			zuck::construct(_m_head->_m_data, zuck::forward<Args>(args)...);
			++_m_cnt;
			return iterator(_m_head);
		}

		inline void __verify_size(const size_type _Newsize)
		{
			auto const _Max = max_size();
			if (_Newsize == _Max) {
				derror(zuck::SEG_LengthTooLong, 
                        "forward_list length too long !");
			}
		}

		inline void __verify_list()noexcept
		{
			if (!empty()) {
				__destroy();
			}
		}

        template<typename ...Args>
        void __construct_val(Args&&... args) {
            if (_m_tail) {
                _m_tail->_m_n = _Node_Alloc::_Allocate(alloc.allocate(1), null, _m_tail);
                _m_tail = _m_tail->_m_n;
                zuck::construct(_m_tail->_m_data);
                return;
            }
            _m_head = _Node_Alloc::_Allocate(alloc.allocate(1));
            _m_tail = _m_head;
            zuck::construct(_m_head->_m_data, zuck::forward<Args>(args)...);
        }

		inline void __construct_n(size_type _Newsize, const T& val) {
			__verify_size(_Newsize);
            _m_cnt = _Newsize;
			for (; _Newsize; --_Newsize) {
				__construct_val(val);
			}
		}

		template<typename PointerType>
		inline void __construct_range(PointerType Begin, PointerType End)
		{
			__verify_list();
			auto const _Newsize = zuck::distance(Begin, End);
			__verify_size(_Newsize);
            _m_cnt = _Newsize;
			for (; Begin != End; ++Begin) {
				__construct_val(*Begin);
			}
		}

		void __destroy_begin()
		{
			zuck::destruct(*(_m_head->_m_data));
			alloc.deallocate(_m_head->_m_data, 1);
			_m_head = _m_head->_m_n;
			_m_head->_m_data = null;
			--_m_cnt;
		}

		void __free_tail_n(size_type _FreeCount)
		{
			for (; _FreeCount; --_FreeCount) {
				__destroy_end();
				_m_tail = _m_tail->_m_p;
			}
		}

		template<typename _Equal>
		bool __not_equal_with(const _Self& other, _Equal _Pr)const noexcept
		{
			_Node_ptr proxy = _m_head;
			for (auto& itm : other) {
				if (proxy->_m_data != itm) {
					return true;
				}
			}
			return false;
		}

		template<typename _Equal>
		bool __equal_with(const _Self& other, _Equal _Pr)const noexcept
		{
			_Node_ptr proxy = _m_head;
			for (auto& itm : other) {
				if (proxy->_m_data != itm) {
					return false;
				}
			}
			return true;
		}
	};


	template<typename T, typename Alloc = zuck::allocator<T>>
    forward_list(T, zuck::size_t)->forward_list<T, Alloc>;

	template<typename T, typename Alloc = zuck::allocator<T>>
    forward_list(T, zuck::size_t, Alloc)->forward_list<T, Alloc>;

	template<typename T, typename Alloc = zuck::allocator<T>>
	forward_list(std::initializer_list<T>)->forward_list<T, Alloc>;

	template<typename T, typename Alloc = zuck::allocator<T>>
	forward_list(std::initializer_list<T>, Alloc)->forward_list<T, Alloc>;

	template<typename InputIterator,
		typename T		= zuck::iter_traits_t<InputIterator>,
		typename Alloc = zuck::allocator<T>,
        zuck::enable_if_t<zuck::is_iterator_v<InputIterator>, int> = 0>
	forward_list(InputIterator, InputIterator)->forward_list<T, Alloc>;

	template<typename T, typename Alloc = zuck::allocator<T>>
	forward_list(forward_list<T> const&)->forward_list<T, Alloc>;

	template<typename T, typename Alloc = zuck::allocator<T>>
	forward_list(forward_list<T>&&)->forward_list<T, Alloc>;
}

